Open shortest path first (OSPF) is an Internal gateway protocol that was designed to be used internally in a single, autonomous system. OSPF uses link state or shortest path first-based technology (as compared to the distance-vector or Bellman-Ford technology found in routing protocols such as routing information protocol (RIP). Individual link state advertisements (LSAs) describe pieces of the OSPF routing domain (autonomous system). These LSAs are flooded throughout the routing domain, forming the link state database. Each router has an identical link state database; synchronization of link state databases is maintained via a reliable flooding algorithm. From this link state database, each router builds a routing table by calculating a shortest-path tree, with the root of the tree being the calculating router itself. This calculation is commonly referred to as the Dijkstra procedure.
LSAs are small. Each advertisement describes a small piece of the OSPF routing domain, such as the neighborhood of a single router, the neighborhood of a single transit network, a single inter-area route or a single external route.
This type of routing protocol requires each router to maintain at least a partial map of the network. When a network link changes state (up to down, or vice versa), an LSA is flooded throughout the network. All the routers note the change, and recompute their routes accordingly. This method is more reliable, easier to debug and less bandwidth-intensive than distance-vector methods. It is also more complex and more computationally- and memory-intensive. OSPF and OSI's IS-IS are link state routing protocols.
Adjacency, as referred to herein, is a relationship formed between selected neighboring OSPF routers for the purpose of exchanging routing information. When the link state databases of two neighboring routers are synchronized, the routers are said to be adjacent. Not every pair of neighboring routers becomes adjacent. The fact that routers are neighbors is not sufficient to guarantee an exchange of link state updates; they must form adjacencies to exchange link state updates. Adjacency is an advanced form of neighborship formed by routers that are willing to exchange routing information after negotiating parameters of such an exchange. Routers reach a FULL state of adjacency when they have synchronized views on a link state database.
Interface type plays a major role in how the adjacencies are formed. For example, neighbors on point-to-point links always try to become adjacent, while routers attached to broadcast media such as Ethernet may choose to become adjacent only with a subset of neighboring routers on the interface.
Once a router decides to form an adjacency with a neighbor, it starts by exchanging a full copy of its link state database. The neighbor, in turn, exchanges a full copy of its link state database with the router. After passing through several neighbor states, the routers become fully adjacent.
As stated above, OSPF is a link state protocol. When an OSPF-compliant router starts to speak with another router, it brings up an adjacency via a database exchange process. The database exchange is an attempt to synchronize the link state database of the two routers. Any missing information is requested from the neighbor. This does not scale, if a routers starts to speak with many other routers. It could potentially request the same information from all the adjacent routers. Each such request results in an LSA update, which must be reliably acknowledged. This results in unnecessary control packet transmissions.
When a router receives from a neighbor a database description (DBD) packet containing LSA descriptions that are not present in its local link state database, the router sends out a link state request (LSREQ) directed towards the neighbor. In the case of multiple adjacencies coming up at the same time, the link state database synchronization process could request the same LSA from multiple peers.
The neighbor replies to these requests in one or more link state update (LSUPD) packets. Each such duplicate request results in a duplicate update from the peer. Each such LSUPD further results in the sending of an acknowledgement (ACK).
The protocol described above becomes expensive in wireless environments, such as mobile, ad hoc networks where not only are unnecessary OSPF packets sent, but these packets can be retransmitted many times due to packet loss. This results in higher control traffic overhead and poor routing convergence. Thus, there is a heartfelt need for reduction and load balancing of link state requests in an OSPF-compliant system of network routers.